package 二维前缀和_二维差分_离散化技巧;

// 利用二维前缀和信息迅速得到二维区域和
// 测试链接 : https://leetcode.cn/problems/range-sum-query-2d-immutable/
public class Code01_PrefixSumMatrix {

    class NumMatrix {

        public int[][] sum;

        public NumMatrix(int[][] matrix) {
            // 行
            int n = matrix.length;
            // 列
            int m = matrix[0].length;
            // 在 第 0 行 和 第 0 列上补 0
            sum = new int[n + 1][m + 1];
            // matrix数组的 第0行第0列 的值 填充到 sum数组的 第1行第1列 的值
            for (int a = 1, c = 0; c < n; a++, c++) {
                for (int b = 1, d = 0; d < m; b++, d++) {
                    sum[a][b] = matrix[c][d];
                }
            }

            // 左上角(0,0)到右下角(i,j)这个范围的累加和
            for (int i = 1; i < n + 1; i++) {
                for (int j = 1; j < m + 1; j++) {
                    sum[i][j] += sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1];
                }
            }
        }

        // 查询左上角(a,b)到右下角(c,d)这个范围的累加和
        // 因为：sum数组进行了补0操作，比 matrix 大了一圈，所以a,b,c,d 要进行 +1 操作
        public int sumRegion(int a, int b, int c, int d) {
            a++; b++; c++; d++;
            return sum[c][d] - sum[c][b - 1] - sum[a - 1][d] + sum[a - 1][b - 1];
        }
    }
}
